package com.lft.linked.list04.stack_linked_list;

/**
 * 链表实现栈
 */
public class StackLinkedListDemo {
	public static void main(String[] args) {
		StackLinkedList stack = new StackLinkedList();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);
		stack.push(6);
		
		stack.displayStack();
		System.out.println("栈顶数据：" + stack.peek());
		
		stack.pop();
		stack.pop();
		stack.pop();
		
		stack.displayStack();
		System.out.println("栈顶数据：" + stack.peek());
	}
}

/**
 * 链表模拟栈
 */
class StackLinkedList {
	private SingleLinkList list;
	
	public StackLinkedList() {
		this.list = new SingleLinkList();
	}
	
	/**
	 * 数据压栈
	 * @param data
	 */
	public void push(int data) {
		list.insertHead(data);
	}
	
	/**
	 * 数据出栈
	 * @return
	 */
	public int pop() {
		LinkNode deleteNode = list.deleteHead();
		if (deleteNode != null) {
			return deleteNode.getIdata();
		} else {
			throw new RuntimeException("栈空");
		}
	}
	
	/**
	 * 显示栈顶数据
	 * @return
	 */
	public int peek() {
		if (!list.isEmpty()) {
			return list.getHead().getIdata();
		} else {
			throw new RuntimeException("栈空");
		}
	}
	
	/**
	 * 判断栈是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return list.isEmpty();
	}
	
	/**
	 * 打印栈
	 */
	public void displayStack() {
		System.out.println("Top -> Bottom");
		list.displayList();
	}
}

/**
 * 单链表
 */
class SingleLinkList {
	//头结点,不存放数据，从头结点出发通过每个结点的next可以遍历整个链表
	private LinkNode head;
	
	public SingleLinkList() {
		head = null;
	}
	
	/**
	 * 判断链表是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return head == null;
	}
	
	/**
	 * 获取链表头节点
	 * @return
	 */
	public LinkNode getHead() {
		return head;
	}
	
	/**
	 * 设置头节点
	 * @param head
	 */
	public void setHead(LinkNode head) {
		this.head = head;
	}
	
	/**
	 * 插入头节点（以数值的形式）
	 * @param data
	 */
	public void insertHead(int data) {
		LinkNode newNode = new LinkNode(data);
		this.insertHead(newNode);
	}
	
	/**
	 * 插入头节点（以节点的形式）
	 * @param newNode
	 */
	public void insertHead(LinkNode newNode) {
		newNode.setNext(head);
		head = newNode;
	}
	
	/**
	 * 删除头节点
	 * @return
	 */
	public LinkNode deleteHead() {
		if (isEmpty()) {
			return null;
		}
		LinkNode oldNode = head;//存储要删除的结点
		head = head.getNext();
		return oldNode;//返回删除的结点
	}
	
	/**
	 * 遍历链表
	 */
	public void displayList() {
		LinkNode temp = head;//获得第一个结点
		while (temp != null) {
			temp.displayNode();
			temp = temp.getNext();//下一个结点
		}
		System.out.println();
	}
	
	/**
	 * 按值查找
	 * @param key
	 * @return
	 */
	public boolean findByval(int key) {
		LinkNode current = head;
		while (current != null) {
			if (current.getIdata() == key) {
				return true;
			}
			current = current.getNext();
		}
		return false;
	}
	
	/**
	 * 按位置查找
	 * @param pos
	 * @return
	 */
	public LinkNode findBypos(int pos) {
		int n = 1;//记录遍历到第几个结点了
		LinkNode current = head;
		while (current != null) {
			if (n == pos) {
				return current;
			}
			current = current.getNext();
			n++;
		}
		return null;
	}
	
	//删除链表中所有值为key的结点
	public void deleteByval(int key) {
		LinkNode previous = head;//存储前一个结点
		LinkNode current = head;
		while (current != null) {
			if (current.getIdata() == key) {
				if (current == head) {
					head = head.getNext();//特殊情况，第一个结点就是我们要删除的那么head后移一下
				}
				previous.setNext(current.getNext());//普通情况
			}
			previous = current;
			current = current.getNext();
		}
	}
	
	//删除指定位置的结点
	public void deleteBypos(int pos) {
		int n = 1;
		LinkNode previous = head;
		LinkNode current = head;
		while (current != null) {
			if (n == pos) {
				if (pos == 1) {
					head = head.getNext();
					return;
				}
				previous.setNext(current.getNext());
			}
			previous = current;
			current = current.getNext();
			n++;
		}
	}
	
	/**
	 * 按位置插入
	 * @param pos
	 * @param newNode
	 */
	public void insertBypos(int pos, LinkNode newNode) {
		if (pos == 0) {//pos为0说明在头部插入结点，直接使用已经实现好的insert()方法
			insertHead(newNode);
			return;
		}
		LinkNode current = findBypos(pos);//根据位置找到该结点
		if (current != null) {//不为null说明查找成功
			newNode.setNext(current.getNext());
			current.setNext(newNode);
		}
	}
	
}

/**
 * 节点类
 */
class LinkNode {
	private int idata;//数据域
	private LinkNode next;//引用域
	
	public LinkNode(int data) {
		this.idata = data;
	}
	
	public int getIdata() {
		return idata;
	}
	
	public void setIdata(int idata) {
		this.idata = idata;
	}
	
	public LinkNode getNext() {
		return next;
	}
	
	public void setNext(LinkNode next) {
		this.next = next;
	}
	
	//打印链结点数据域内容
	public void displayNode() {
		System.out.print(idata + "  ");
	}
	
	@Override
	public String toString() {
		return "LinkNode [" +
				"idata=" + idata +
				']';
	}
}

